#ifndef HUFFMAN_MINHEAP_H
#define HUFFMAN_MINHEAP_H
template<typename Type>
class MinHeap
{
public:
	MinHeap(Type heap[],int n);		//initialize heap by a array
	~MinHeap()
	{
		delete[] m_pheap;
	}

public:
	bool Insert(const Type item);
	bool DeleteMin(Type &first);

private:
	void Adjust(const int start, const int end);	//adjust the elements from start to end


private:
	const int m_nMaxSize;	
	Type *m_pheap;
	int m_ncurrentsize;
};

template<typename Type> 
void MinHeap<Type>::Adjust(const int start, const int end)
{
	int i = start,j = i*2+1;
	Type temp=m_pheap[i];
	while(j <= end)
	{
		if(j<end && m_pheap[j]>m_pheap[j+1])
		{
			j++;
		}
		if(temp <= m_pheap[j])
		{
			break;
		}
		else
		{
			m_pheap[i] = m_pheap[j];
			i = j;
			j = 2*i+1;
		}
	}
	m_pheap[i] = temp;
}

template<typename Type> 
MinHeap<Type>::MinHeap(Type heap[], int n):m_nMaxSize(n)
{
	m_pheap = new Type[m_nMaxSize];
	for(int i=0; i<n; i++)
	{
		m_pheap[i] = heap[i];
	}
	m_ncurrentsize = n;
	int pos=(n-2)/2;	//Find the last tree which has more than one element;
	while(pos>=0)
	{
		Adjust(pos, n-1);
		pos--;
	}
}

template<typename Type> 
bool MinHeap<Type>::DeleteMin(Type &first)
{
	first = m_pheap[0];
	m_pheap[0] = m_pheap[m_ncurrentsize-1];
	m_ncurrentsize--;
	Adjust(0, m_ncurrentsize-1);
	return 1;
}

template<typename Type> 
bool MinHeap<Type>::Insert(const Type item)
{
	if(m_ncurrentsize == m_nMaxSize)
	{
		cerr<<"Heap Full!"<<endl;
		return 0;
	}
	m_pheap[m_ncurrentsize] = item;
	int j = m_ncurrentsize, i = (j-1)/2;
	Type temp = m_pheap[j];
	while(j > 0)
	{
		if(m_pheap[i] <= temp)
		{
			break;
		}
		else
		{
			m_pheap[j] = m_pheap[i];
			j = i;
			i = (j-1)/2;
		}
	}
	m_pheap[j] = temp;
	m_ncurrentsize++;
	return 1;
}

#endif